# -*- coding: utf-8 -*-
# @Time : 2024/1/31 18:52
# @Author : ZH
# @File : 31.py
# @Software: PyCharm
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        # 寻找影响升序的数字
        i = len(nums) - 2
        while i >= 0:
            if nums[i] < nums[i+1]:
                break
            else:
                i -= 1
        if i >= 0:

            # 找到这个值以后 寻找比这个值大的第一个值
            j = len(nums) - 1
            while j >= 0:
                if nums[j] > nums[i]:
                    nums[j], nums[i] = nums[i], nums[j]
                    break
                else:
                    j -= 1

        # 找到这个两个值以后 将 i - 1 到 -1倒置
        left, right = i + 1, len(nums) - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1


if __name__ == '__main__':
    nums = [1,2,3]
    so = Solution()
    so.nextPermutation(nums=nums)
    print(nums)

